package cn.dapeng.tree.binary;

/**
 * 求一棵树的最大距离
 * 1. 经过头节点的最大距离：左树高度+右树高度+1
 * 2. 左树的最大距离
 * 3. 右树的最大距离
 * <p>
 * 三种情况中求最大值,就是这颗树的最大距离
 */
public class MaxDistance {


    public static int maxDistance(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxDistance;
    }

    public static Info process(TreeNode x) {
        if (x == null) {
            return new Info(0, 0);
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int p1 = leftInfo.maxDistance;
        int p2 = rightInfo.maxDistance;
        int p3 = leftInfo.height + rightInfo.height + 1;
        int maxDistance = Math.max(p1, Math.max(p2, p3));

        return new Info(maxDistance, height);
    }

    public static class Info {
        public int maxDistance;
        public int height;

        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }
}
